#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //dp[i]第i天后的最大利润
        //状态 "第i天后" [0]:持有股票 [1]:不持有股票 [2]:冷冻期
        //状态机 状态转移方程: dp[i][0]=max(dp[i-1][0],dp[i-1][1]-p[i])
        //                    dp[i][1]=max(dp[i-1][1],dp[i-1][2])
        //                    dp[i][2]=dp[i-1][0]+p[i]
        vector<vector<int>>dp(prices.size(),vector<int>(3,0));
        dp[0][0]-=prices[0];
        for(int i=1;i<dp.size();i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);
            dp[i][1]=max(dp[i-1][1],dp[i-1][2]);
            dp[i][2]=dp[i-1][0]+prices[i];
        }
        return *max_element(dp.back().begin(),dp.back().end());
    }
};